#include <iostream>
#include <algorithm>
#define MAX_N 60
#define MAX_V 32000
using namespace std;


int main()
{
    int n,v;
    //int c[MAX_N] = {0}, w[MAX_N] = {0};
    cin >> v >> n;
    int w[n+1][4], c[n+1][4];
    fill(w[0], w[0]+(n+1)*4, 0);
    fill(c[0], c[0]+(n+1)*4, 0);
    int mai = 0, aff = 1;
    for (int i=1; i<=n; ++i)
    {
        int inc, inw, tom;
        cin >> inc >> inw >> tom;
        inw = inc * inw;
        if(tom==0)
        {
            ++mai;
            w[mai][0] = inw;
            c[mai][0] = inc;
            aff = 1;
        }
        else
        {
            if (w[tom][3]==0) w[tom][3] += w[mai][0];
            if (c[tom][3]==0) c[tom][3] += c[mai][0];

            w[tom][aff] += inw + w[mai][0];
            w[tom][3] += inw;
            c[tom][aff] += inc + c[mai][0];
            c[tom][3] += inc;
            aff = 2;
        }
        //cin >> c[i] >> w[i];
        //w[i] = c[i];
        //w[i] = c[i] * w[i];
    }
    int bag[v+1] = {0};
    for (int i=1; i<=mai; ++i)
        for (int j=v; j>=0; --j)
            for (int k=0; k<4; ++k)
                if (j>=c[i][k]) bag[j] = max(bag[j], bag[j-c[i][k]] + w[i][k]);

    cout << bag[v];
    return 0;
}

/*
1000 5
800 2 0
400 5 1
300 5 1
400 3 0
500 2 0

2200
*/
